import java.util.Arrays;
import java.util.BitSet;


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(4);
//        ListNode l3 = new ListNode(6);
//        ListNode l4 = new ListNode(8);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
        ListNode node = new Solution().insertNode(l1, 0);
        System.out.println(node);
    }

    public ListNode insertNode(ListNode head, int val) {
        // write your code here
        ListNode node = new ListNode(val);
        if(head==null){
            return node;
        }

        if (head.val >= val) {
            node.next = head;
            return node;
        }
        ListNode tempNode = head;
        while (tempNode != null) {
            if (tempNode.val <= val && (tempNode.next == null || tempNode.next.val >= val)) {
                node.next = tempNode.next;
                tempNode.next = node;
                return head;
            }
            tempNode = tempNode.next;
        }
        return head;
    }

    public long arrayGame(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        long step = 0L;
        for (int i = 0; i < arr.length; i++) {
            step += arr[i] - min;
        }
        return step;
    }

    public long arrayGame1(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        long step = 0L;
        for (int i = 0; i < arr.length; i++) {
            step += arr[i] - min;
        }
        return step;
    }

    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A.length == 0 || A[0] > target) {
            return 0;
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] == target) {
                return i;
            } else {
                if (i == A.length - 1) {
                    return A.length;
                }
                if (A[i] < target && A[i + 1] > target) {
                    return i + 1;
                }
            }
        }
        return 0;
    }

    public int deduplication(int[] nums) {
        // write your codehere
        if (nums.length < 2) {
            return nums.length;
        }
        BitSet bitSet = new BitSet();
        int left = nums.length - 1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            if (bitSet.get(v)) {
                int leftV = nums[left];
                while (bitSet.get(leftV) && left > i) {
                    left--;
                    leftV = nums[left];
                }
                if (left > i) {
                    nums[i] = nums[i] ^ nums[left];
                    nums[left] = nums[i] ^ nums[left];
                    nums[i] = nums[i] ^ nums[left];
                    bitSet.set(nums[i]);
                    count++;
                }
            } else {
                bitSet.set(v);
                count++;
            }
        }
        return count;
    }

    public int getAns(int[] a) {
        // write your code here
        if (a.length < 2) {
            return a.length;
        }
        int[] bit = new int[100000];
        for (int i = 0; i < a.length; i++) {
            bit[a[i]] = i;
        }
        Arrays.sort(a);
        int index = a[(a.length - 1) / 2];
        return bit[index];
    }
}